Sorting ソート 整列
整列を行うアルゴリズム Algorithms
全順序 total order
定義されているデータの集合に対してその要素を一定の順序に従って一列に並べる
昇順 ascending order
値が小さなものから大きなものへ順に並べる
降順 descending order
値が大きなものから小さいものへと順に並べる
評価軸
時間計算量 time complexity
in-place Algorithms
安定性 Algorithms
種類
比較ソート comparison sorts
O(n**2)
Bubble Sort バブルソート
Selection Sort 選択ソート
挿入ソート Insertion sort
Shellsort シェルソート
Quicksort クイックソート
O(n log n)
Heap Sort ヒープソート
Merge Sort マージソート
非比較ソート non-comparison sorts
O(n)
Bucket Sort バケットソート
基数ソート radix sort
計数ソート counting sort
実行方法
内部ソート internal sorting
整列作業のすべてを主記憶上で実行
外部ソート external sorting
外部の補助記憶を用いて整列作業実行
用途
大量の二分探索 Binary searchの前処理
特定キーで並び替え
Task Scheduling タスクスケジューリング
例CG Computer graphicsのレンダリング Rendering順
上位k個が欲しい
ビームサーチ
Deep Learning
情報落ちを減らす
貪欲法の前処理
様々なアルゴリズム Algorithmsの前処理
JavaScript
sort()
比較関数なしだと，要素が文字列になる
ソートを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
JavaScript つい忘れてしまう配列のソート方法 - Qiita
ライブラリ
snovakovic/fast-sort: Blazing fast array sorting with TypeScript support.
参考
💯ソートを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
途中記録ソートを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
競技プログラマが知るべき97のこと　許されるときはいつでも入力をソートしよう (01/97) - aizuzia